package com.bing.java.search;

/**
 * 二分查找的2种实现方式
 * @author bing
 *
 * 2019年11月18日 下午5:02:01
 */
public class SearchBinary {

	public static void main(String[] args) {
		int [] num = {3,5,8,9,12,22,23,27,28};
		int searchData = 23;
		int result = binarySearchByWhile(num,searchData);
		
		int low = 0;
		int high = num.length -1;
		int result2 = binarySearchByDiGui(num,searchData,low,high);

		System.out.println(result);
		System.out.println(result2);

	}


	/**
	 * 循环查找
	 * @param num
	 * @param searchData
	 * @return
	 */
	private static int binarySearchByWhile(int[] num, int searchData) {
		int low = 0;
		int high = num.length -1;
		while(low < high){
			int middle = (low+high)/2;
			if (searchData == num[middle]){
				return num[middle];
			} else if (searchData < num[middle]){
				high = middle - 1;
			} else {
				low = middle + 1;
			}
		}
		return -1;
	}
	
	/**
	 * 二分查找递归
	 * @param num
	 * @param searchData
	 * @param low
	 * @param high
	 * @return
	 */
	private static int binarySearchByDiGui(int[] num, int searchData, int low, int high) {
		int middle = (low+high) / 2;
		if (searchData < num[low] || searchData > num[high] || low > high) {
			return  -1;
		}
		if (searchData == num[middle]){
			return num[middle];
		} else if (searchData < num[middle]){
			return binarySearchByDiGui(num,searchData,low,middle - 1);
		} else {
			return binarySearchByDiGui(num,searchData, middle + 1,high);
		}
	}
}
